package 简单.贪心思想;

import java.util.Arrays;

/**
 * 由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:
 * 如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I' 
 * 如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D' 
 * 给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/di-string-match
 */
public class 增减字符串匹配_942 {

    public static void main(String[] args) {

        System.out.println(Arrays.toString(diStringMatch("DDI")));

    }

    /**
     * 贪心思想+双指针
     * 对于每一个perm[i]，只有 perm[i+1] 对它有限制
     * 如果 perm[i] < perm[i + 1] ，那么贪心的取 perm[i] = 最小的那个数字，是一定符合条件的
     * 如果 perm[i] > perm[i + 1] ，那么贪心的取 perm[i] = 最大的那个数字，是一定符合条件的
     * <p>
     * 0 1 2 3 4
     * IDID
     * 0 4 1 3 2
     *
     * @param s
     * @return
     */
    public static int[] diStringMatch(String s) {
        int[] perm = new int[s.length() + 1];
        int min = 0, max = s.length();
        char[] chars = s.toCharArray();  // 小技巧: 减少时间复杂度
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == 'I') {
                perm[i] = min;
                min++;
            } else {
                perm[i] = max;
                max--;
            }
        }
        perm[perm.length - 1] = max;
        return perm;
    }

}
